#define _CRT_SECURE_NO_WARNINGS 1
#include <algorithm>
using namespace std;
  struct TreeNode {
 	int val;
 	struct TreeNode *left;
 	struct TreeNode *right;
 	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  };
 
class Solution {
public:
    bool sub(TreeNode* cur, int* high)
    {
        if (!cur)
        {
            *high = 0;
            return true;
        }
        int Lhigh = 0, Rhigh = 0;
        if (!sub(cur->left, &Lhigh))
        {
            return false;
        }
        if (!sub(cur->right, &Rhigh))
        {
            return false;
        }
        *high = Lhigh > Rhigh ? Lhigh + 1 : Rhigh + 1;
        if (abs(Lhigh - Rhigh) > 1) return false;
        return true;
    }
    bool IsBalanced_Solution(TreeNode* pRoot)
    {
        int high;
        return sub(pRoot, &high);
    }
};